This invention relates to network flow, and more particularly to the application of network flow techniques to constrained optimization problems.
Many practical problems can be formulated and solved using network flow techniques. Some examples of such problems are: finding the fastest route between two locations in a city, determining the most efficient way to transport products from distribution centers to clients, and how best to route electricity from generating stations to buildings in a city. At a high-level, network flow techniques are applied as follows: First, the problem to be solved is analyzed and a xe2x80x9cflow networkxe2x80x9d representing the problem is formulated. A flow network is a directed graph consisting of a set of nodes and edges. At least one of the nodes is designated as a source node; at least one of the nodes is designated as a sink node. Edges in the graph have a property called capacity and may also have a property called cost.
Intuitively, edges can be viewed as pipes and edge capacities represent the amount of fluid that may be sent through a pipe, and edge costs represent the cost of sending fluid through a pipe. Prior art techniques can be used to find the minimum cost, maximum network flow through the network from the source node(s) to the sink node(s). The solution to a network flow problem is a flow value for each edge (possibly zero). The network flow solution is translated into a solution for the original problem being solved; for example, flow along a particular edge in the network may imply the shipping of goods from a particular distribution center to a particular client. One limitation of the applicability of network flow techniques however is that they cannot be applied to problems having certain types of constraints. This is because these prior art techniques require that the network for which a flow is computed must be static. This eliminates the possibility of having dependencies in the flow network. Unfortunately, real life problems often have constraints and consequently, there are many problems to which network flow techniques cannot be applied.
A specific example will be used to illustrate the issue. In many engineering and operations research applications, it is important to be able to determine the optimal matching between a set of objects (e.g., electronic components, resources, people, etc.) with a set of slots (e.g., physical locations, tasks, buildings, people, etc.). An example is illustrated in FIG. 1A. It comprises a set of objects 102, 103, . . . , and 104 and a set of slots 106, 107, 108, . . . , and 109. The number of slots may be the same as or more than the number of objects. As a result, every object should match with one and only one of the slots. FIG. 1A shows a matching in which objects 102-104 are matched with slots 107, 106 and 109, respectively. Each edge in FIG. 1A has an associated cost, with the aim being to match the maximum number of objects to slots such that the cost of the matching is minimized. One method to find the minimum cost, maximum matching is the so-called xe2x80x9cHungarian algorithmxe2x80x9d. Information on this algorithm can be found in D. B. West, xe2x80x9cIntroduction to Graph Theory,xe2x80x9d Prentice Hall, Upper Saddle River, N.J., 2001.
It has been realized that the determination of the optimal matching is similar to the determination of maximum size, minimum cost flow in a flow network. FIGS. 1B shows a network 130. Elements that are substantially the same in FIGS. 1A-1B share the same reference numerals. In FIG. 1B, network 130 contains a xe2x80x9cvirtual sourcexe2x80x9d 132 that originates flows to various objects in a source vertex set 134. Virtual source 132 is not a physical source, and it is added to facilitate the determination of the optimal matching. The flows from the selected slots are collected by a xe2x80x9cvirtual sinkxe2x80x9d 138. Virtual sink 138 is not a physical sink, and it is added to complete the flow.
The possible connections between the objects, slots, virtual source, and virtual sink are called xe2x80x9cedges.xe2x80x9d FIG. 1B shows the set of edges. Three of them are shown as reference numerals 142-144. There is one requirement in the flow network 130 for the matching problem: edges do not exist between objects and between slots. Thus, there is no edge between objects 102-104. Similarly, there is no edge between slots 106-109. Each edge is associated with a xe2x80x9ccapacityxe2x80x9d and a xe2x80x9ccost.xe2x80x9d Various prior art methods have been developed to find edges between virtual source 132 and virtual sink 138 that can deliver the maximum size, minimum cost flow from the source to the sink. Edges between vertex sets 134 and 136 with non-zero flow constitute the edges of a maximum size, minimum cost matching of objects to slots. These edges correspond to the optimal matching between objects and slots in FIG. 1A. Information on various network flow techniques can be found in R. K. Ahuja, T. L. Magnanti and J. B. Orlin, xe2x80x9cNetwork Flows,xe2x80x9d Prentice Hall, 1993.
Prior art methods assume that the objects in vertex sets 134 and 136 are independent. However, in many applications (such as computer-aided design), some of the objects are related to each other. An example in computer-aided design is the placement of low voltage differential signaling (LVDS) input-output (I/O) ports (i.e., objects) in field programmable gate array (FPGA) devices. In an FPGA, there are many input-output block (IOB) sites (i.e., slots). Because LVDS is a differential standard, each LVDS input or output is built using two adjacent IOB sites whereas inputs or outputs of other I/O standards require only a single IOB. Consequently, the differential signals of LVDS need to be placed to adjacent IOBs.